package Solutions;


/**
 * @Classname MaxSumOfAnArray
 */
public class MaxSumOfAnArray {

    private static class Result {
        int start;
        int end;
        int sum;

        public Result(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "start=" + start +
                    ", end=" + end +
                    ", sum=" + sum +
                    '}';
        }
    }

    public int maxSumOfAnArray(int[] array) {
        if (array == null || array.length == 0) return 0;
        int currentSum = 0;
        int maxSum = array[0];
        for (int value : array) {// 遍历整个数组，累加求和得到当前最大的子数组之和
            if (currentSum >= 0) currentSum += value;// 如果当前的子数组之和大于等于0
            else currentSum = value;// 将当前的数组元素作为新的子数组的第一个元素
            maxSum = Math.max(maxSum, currentSum);// 将之前的最大值与目前的最大值比较，取出较大值
        }
        return maxSum;
    }

    public Result maxSumOfAnArrayWithIndex(int[] array) {
        if (array == null || array.length == 0) return null;
        int currentSum = 0;
        int maxSum = array[0];
        int start = 0, end = 0;
        for (int i = 0; i < array.length; i++) {
            if (currentSum >= 0) {
                currentSum += array[i];
            } else {
                currentSum = array[i];
                start = i;
            }
            if (maxSum < currentSum) {
                maxSum = currentSum;
                end = i;
            }
        }
        return new Result(start, end, maxSum);
    }


    public static void main(String[] args) {
        int[] array = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println(new MaxSumOfAnArray().maxSumOfAnArray(array));
        System.out.println(new MaxSumOfAnArray().maxSumOfAnArrayWithIndex(array));
    }
}
